//https://leetcode.cn/problems/trapping-rain-water/submissions/587974013/
class Solution {
public:
    int trap(vector<int>& height) {
        long long  ret = 0;
        int left = 0, right = height.size() - 1;
        int leftmax = height[left], rightmax = height[right];
        while (left < right)
        {
            if (leftmax < rightmax)
            {
                ret += leftmax - height[left];
                left++;
                leftmax = max(leftmax, height[left]);
            }
            else {
                ret += rightmax - height[right];
                right--;
                rightmax = max(rightmax, height[right]);
            }
        }
        return ret;
    }
};